package org.raymond.iworks.study.basic.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而
 * 治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = newArr();
        //arr = new int[]{3, 9, -1, 10, -2};
        //arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        //arr = new int[]{8,4,5,7,1,3,6,2};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        int[] cloned = Arrays.copyOf(arr, arr.length);
        int[] tmp = new int[arr.length];
        long start = System.nanoTime();
        mergeSort(arr, 0, arr.length-1, tmp);
        long end = System.nanoTime();
        System.out.printf("归并排序结果:%s\n", Arrays.toString(arr));
        // post: 22,153,200 纳秒,约22毫秒, 100,000个元素
        // post: 22,087,008,200 纳秒,约22秒, 100,000,000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        SelectSortTest.jdkSort(cloned);
        end = System.nanoTime();
        System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 47,220,300 纳秒, 约50毫秒, 100,000个元素的数组
        // post: 15,091,233,500 纳秒, 约15秒, 1亿个元素
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static int[] newArr(){
        int[] arr = new int[100_000_000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*Integer.MAX_VALUE);
        }
        return arr;
    }

    public static void mergeSort(int[] arr, int left, int right, int[] tmp){
        if(left<right){
            int mid = (left+right)/2;
            // 向左递归分解
            mergeSort(arr, left, mid, tmp);
            // 向右递归分解
            mergeSort(arr, mid+1, right, tmp);
            // 合并
            merge(arr, left, mid, right, tmp);
        }
    }

    /**
     * @param src 待合并的数组,包含左右两个有序序列
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边有序序列的结束索引
     * @param tmp 合并时的中转数组
     */
    public static void merge(int[] src, int left, int mid, int right, int[] tmp){
        int i=left;
        //右边有序序列的初始索引
        int j=mid+1;
        //指向tmp数组的当前索引
        int t=0;
        // 1,先把左右两边有序序列的数据按规则填充到tmp数组,直到左右两边的有序序列,有一边处理完毕为止.
        while(i<=mid && j<=right){
            if(src[i]<=src[j]){
                tmp[t]=src[i];
                i++;
                t++;
            }else{
                tmp[t]=src[j];
                j++;
                t++;
            }
        }
        // 2,如果左边有剩余数据,则将剩余数据依次填入tmp数组.
        while(i<=mid){
            tmp[t]=src[i];
            i++;
            t++;
        }
        // 如果右边有剩余数据,则将剩余数据依次填入tmp数组.
        while(j<=right) {
            tmp[t] = src[j];
            j++;
            t++;
        }
        // 3,将tmp数组的元素覆盖到src上.
        t=0;
        /**
         * 第1次合并:tmpleft=0,right=1
         * 第2次合并:tmpleft=2,right=3
         * 第3次合并:tmpleft=0,right=3
         * 最后依次合并:tmpleft=0,right=7
         * 一共合并数组长度-1次.
         */
        int tmpleft = left;
        System.out.printf("tmpleft:%d, right:%d\n", tmpleft, right);
        while(tmpleft<=right){
            src[tmpleft]=tmp[t];
            tmpleft++;
            t++;
        }
    }
}
